import java.util.*;
public class Main{
    public static boolean[][] fn;
    public static int n;
    public static int m;
    public static int bfs(int[][] arr,int x,int y){
        int[] dy={0,0,-1,1};
        int[] dx={1,-1,0,0};
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{x,y});
        fn[x][y]=true;
        int count=0;
        while(!q.isEmpty()){
            int size=q.size();
            count++;
            while(size-->0){
                int[] ret=q.poll();
                for(int i=0;i<4;i++){
                    int xt=ret[0]+dx[i];
                    int yt=ret[1]+dy[i];
                    if(xt>=0&&xt<n&&yt>=0&&yt<m&&arr[xt][yt]==4) return count;
                    if(xt>=0&&xt<n&&yt>=0&&yt<m&&arr[xt][yt]==0&&!fn[xt][yt]){
                        q.add(new int[]{xt,yt});
                    }
                }
            }
        }
        return -1;
    }
    public static long minimumSteps(String s) {
        char[] arr=s.toCharArray();
        int count=0;
        int n=arr.length;
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(arr[j-1]>arr[j]){
                    char temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                    count++;
                }
            }
        }
        for(int i=0;i<n;i++){
            System.out.print(" "+arr[i]);
        }
        return count;
    }
    public static String minWindow(String s, String t) {

        int left=0;
        int m=t.length();
        int n=s.length();
        if(m>n) return "";
        int[] hash=new int[128];
        int[] hash1=new int[128];
        int len=Integer.MAX_VALUE;
        int strat=-1;
        for(int i=0;i<t.length();i++) hash[t.charAt(i)]++;
        int count=0;
        for(int i=0;i<s.length();i++){
            hash1[s.charAt(i)]++;
            if(hash1[s.charAt(i)]<=hash[s.charAt(i)]) count++;
            while(count>=m){
                if((i-left+1)<len){

                    len=i-left+1;
                    strat=left;
                }
                char ch=s.charAt(left);
                if(hash1[ch]<=hash[ch]) count--;
                hash1[ch]--;
                left++;
            }

        }
        System.out.print(strat+" "+len);
        if(strat==-1) return "";
        else return s.substring(strat,strat+len);
    }
    public static int pivotIndex(int[] nums) {
        int n=nums.length;
        int[] dp=new int [n+2];
        for(int i=0;i<n;i++){
            dp[i+1]=dp[i]+nums[i];
        }
        int i=1;
        for(;i<=n;i++){
            if(dp[i-1]==dp[n]-dp[i]) {
                System.out.println(22222);
                return i-1;
            }

        }
        return -1;
    }
    public static int findMaxLength(int[] nums) {

        int ret = 0;
        for (int j = 0; j < nums.length; j++) {
            int a = 0;
            int b = 0;
            for (int i = j; i < nums.length; i++) {
                if (nums[i] == 1)
                    a++;
                else
                    b++;
                if (a == b)
                    ret = Math.max(ret,a + b);

            }
        }

        return ret;
    }
    public static String modifyString(String s) {
        char[] ch=s.toCharArray();
        int n=s.length();
        for(int i=0;i<n;i++){
            if(ch[i]=='?'){
                for(char ch1='a';ch1<'z';ch1++){
                    if((i==0||ch1!=ch[i-1])&&(i==n-1||ch1!=ch[i+1]))
                    {
                        ch[i]=ch1;
                        break;
                    }
                }
            }
        }
        String ret=new String(ch);
        return ret;
    }
    public static String multiply(String num1, String num2) {
        StringBuffer sb1=new StringBuffer(num1);
        StringBuffer sb2=new StringBuffer(num2);
        sb1.reverse();
        sb2.reverse();
        int n=sb1.length();
        int m=sb2.length();
        int[] dp=new int[m+n];


        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int a=sb1.charAt(i)-'0';
                int b=sb2.charAt(j)-'0';
                dp[i+j]+=a*b;
            }
        }
        StringBuffer sb=new StringBuffer();
        int tem=0;
        for(int i=0;i<m+n;i++){
            int a=(tem+dp[i])%10;
            tem=(tem+dp[i])/10;
            String S=Integer.toString(a);
            sb.append(S);
        }

        while(sb.length()>1){
            if(sb.charAt(sb.length()-1)=='0'){
                sb.deleteCharAt(sb.length()-1);
            }else break;
        }
        return sb.reverse().toString();
    }
    public static String decodeString(String s) {

            Stack<Character> st=new Stack<>();
            Stack<Integer> st1=new Stack<>();
            for(int i=0;i<s.length();){
                if(s.charAt(i)>='0'&&s.charAt(i)<='9') {
                    int sum=0;
                    while(i<s.length()&&s.charAt(i)>='0'&&s.charAt(i)<='9'){

                        sum=sum*10+s.charAt(i)-'0';
                        i++;
                    }
                    st1.push(sum);
                }
                else if(s.charAt(i)!=']') {

                    st.push(s.charAt(i));
                    i++;
                }
                else{
                    StringBuffer sb=new StringBuffer();
                    while(st.peek()!='['){
                        sb.append(st.pop());
                    }
                    st.pop();
                    StringBuffer tem=new StringBuffer();
                    int size=st1.pop();
                    while(size-->0){
                        tem.append(sb);
                    }
                    for(int j=tem.length()-1;j>=0;j--){
                        st.push(tem.charAt(j));
                    }
                    i++;
                }

            }
            StringBuffer tem=new StringBuffer();
            while(!st.isEmpty()){
                tem.append(st.pop());
            }
            return tem.reverse().toString();
        }
       public static int[] tem;
public  static void sort(int[] arr,int left,int right){
       if(left>=right) return;
       int mid=(left+right)/2;
       sort(arr,left,mid);
       sort(arr,mid+1,right);
       int l=left,r=mid+1,i=0;
       while(l<=mid&&r<=right){
           if(arr[l]<arr[r]){
               tem[i++]=arr[l++];
           }else {
               tem[i++]=arr[r++];
           }

       }
       while(l<=mid) tem[i++]=arr[l++];
       while(r<=right) tem[i++]=arr[r++];
       for(int j=left;j<=right;j++){
           arr[j]=tem[j-left];
       }
}
public static  int hole(int[] arr,int left,int right){
    int temp=arr[left];
   while(left<right){
       while (right>left&&arr[right]>=temp) right--;
       if(right>=left) arr[left]=arr[right];
       while (left<right&&arr[left]<temp) left++;
       if(left<=right) arr[right]=arr[left];
   }
   arr[left]=temp;
   return left;
}
public  static  int bing(int[] arr,int left,int right){
    int temp=arr[left];
    int l=left,r=right;
    while(l<r){
        while(r>l&&arr[r]>=temp) r--;
        while(l<r&&arr[l]<temp) l++;
        if(l<r){
            temp=arr[r];
            arr[r]=arr[l];
            arr[l]=temp;
        };
    }
    arr[l]=temp;
    return left;
}
  public  static  void quickSort(int[] arr,int left,int right){
    if(left>=right) return;
        int index=bing(arr,left,right);
        quickSort(arr,left,index-1);
        quickSort(arr,index+1,right);

  }
  public  static void sitdown(int[] arr,int parents,int end){
      int chrild=2*parents+1;
    while(chrild<=end){

        if(chrild+1<=end&&arr[chrild]<arr[chrild+1]) chrild=chrild+1;
        if(arr[parents]>arr[chrild]) break;
        else {
            int temp=arr[chrild];
            arr[chrild]=arr[parents];
            arr[parents]=temp;
            parents=chrild;
            chrild=2*parents+1;
        }
    }
  }
  public  static void crateHeap(int[] arr){
         for(int i=arr.length/2-1;i>=0;i--){
             sitdown(arr,i,arr.length-1);
         }
  }
  public  static  void heapSort(int[] arr){
          crateHeap(arr);
        for(int i=arr.length-1;i>0;i--){
            int tem=arr[i];
            arr[i]=arr[0];
            arr[0]=tem;
            sitdown(arr,0,i-1);
        }

  }
    public static int lengthOfLongestSubstring(String s) {
        int n=s.length();
        Set<Character> hash=new HashSet<>();
        int left=0;
        int ret=0;
        for(int i=0;i<n;i++){
            char ch=s.charAt(i);
            if(hash.contains(ch)){
                while(left<i&&hash.contains(ch)){
                    hash.remove(left);
                    left++;
                }
            }
            hash.add(ch);
            ret=Math.max(ret,i-left+1);
        }
        return ret;
    }
    public static void main(String[] args){
       String S="dvdf";
        System.out.println(lengthOfLongestSubstring(S));
        int[] arr=new int[]{12,5,9,4,45,6,8,11,56,89,2,78,45};

       heapSort(arr);
        int n=arr.length;
        tem=new int[n];
        for(int j=0;j<n;j++){
            System.out.print(arr[j]+" ");
        }
        quickSort(arr,0,n-1);
        for(int j=0;j<n;j++){
           System.out.print(arr[j]+" ");
       }
        Map<String,Integer> hashMap=new HashMap<>();

        PriorityQueue<Map.Entry<String,Integer>> pq=new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){
            public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
               if(o1.getValue()==o2.getValue()) return o2.getKey().compareTo(o1.getKey());
               else return o1.getValue()-o2.getValue();

            }
        });
//        String s="100[leetcode]";
//        System.out.println(decodeString(s));
//        ArrayList<Pair<Integer, Integer>> list=new ArrayList<Pair<Integer,Integer>>();
//         list.add(new Pair<Integer,Integer>(1,2));
//       String num1="123";
//       String num2="456";
//
//        System.out.println(multiply(num1,num2));
//        int[] arr={0,0,1,0,0,0,1,1};
//      int a= findMaxLength(arr);
//        System.out.println(a);
//        String s="ADOBECODEBANC";
//        String t="ABC";
//        System.out.println(minWindow(s, t));
//        Set<Integer> set=new HashSet<>();
//        String ret="100";
//        long start=minimumSteps(ret);
//        System.out.println(start);
//        Scanner in=new Scanner(System.in);
//        n=in.nextInt();
//        m=in.nextInt();
//        int[][] arr=new int[n][m];
//        for(int i=0;i<n;i++){
//            for(int j=0;j<m;j++){
//                arr[i][j]=in.nextInt();
//            }
//        }
//        int count=0;
//        fn=new boolean[n][m];
//        for(int i=0;i<n;i++){
//            for(int j=0;j<m;j++){
//                if(arr[i][j]==3)  count= bfs(arr,i,j);
//            }
//        }
//        if(count==-1) System.out.println("unreachable");
//        else System.out.println(count);

    }
}